package _26_二叉搜索树与双向链表;
/*
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点，只能调整树中结点指针的指向。
 */

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}

public class Solution {
    public TreeNode Convert(TreeNode pRootOfTree) {
        //如果根为null，返回null
        if (pRootOfTree == null) {
            return null;
        }
        //得到左子树转换后的链表的头部
        TreeNode head = Convert(pRootOfTree.left);
        //循环得到链表的尾部
        TreeNode p = head;
        while (p != null && p.right != null) {
            p = p.right;
        }
        //将转换后的尾部赋值给root.left
        pRootOfTree.left = p;
        //左子树转换后的头不空,说明p不是null，

        if (head != null) {

            p.right = pRootOfTree;
        }
        //否则head为root
        else {
            head = pRootOfTree;
        }

        TreeNode right = Convert(pRootOfTree.right);

        pRootOfTree.right = right;
        if (right != null) {
            right.left = pRootOfTree;
        }
        return head;
    }

    //链表尾部
    TreeNode tail = null;
    //返回的链表头部
    TreeNode res = null;

    public TreeNode Convert2(TreeNode pRootOfTree) {
        ConvertSub(pRootOfTree);
        return res;
    }

    private void ConvertSub(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return;
        }
        //将当前节点的左节点进行排序
        ConvertSub(pRootOfTree.left);
        //第一次时候初始化tail和res
        if (tail == null) {
            tail = pRootOfTree;
            res = pRootOfTree;

        } else {
            //实现双向链表，并更新tail
            tail.right = pRootOfTree;
            pRootOfTree.left = tail;
            tail = pRootOfTree;
        }
        ConvertSub(pRootOfTree.right);
    }
}
